package base.internal;

import java.util.LinkedList;
import java.util.List;

import util.StringTool;

import base.Sort;

public class ConcurrentMergeSort implements Sort, Runnable {

	//attributes of a task
	private String [] array;
	private int begin;
	private int end;
	
	@Override
	public String[] sort(List<String> lines, String separator) {

		int size = lines.size();
		String[] g = new String[size];
		g = lines.toArray(g);
		String[] s;
		for (int i = 0; i < size; i++) {
			s = g[i].split(separator);
			sort(s, 0, s.length - 1);
			g[i] = StringTool.arrayToString(s, separator);
		}

		sort(g, 0, size - 1);

		return g;
	}

	public void sort(String[] line, int begin, int end) {
		if (begin == end)
			return;

		int middle = (begin + end) / 2;

		if(middle - begin > 50){ // Limits the number of tasks.
		
		ConcurrentMergeSort leftTask = new ConcurrentMergeSort();
		leftTask.setArray(line);
		leftTask.setBegin(begin);
		leftTask.setEnd(middle);
		
		ConcurrentMergeSort rightTask = new ConcurrentMergeSort();
		rightTask.setArray(line);
		rightTask.setBegin(middle + 1);
		rightTask.setEnd(end);
		
		Thread t1 = new Thread(leftTask);
		Thread t2 = new Thread(rightTask);
		
		t1.start();
		t2.start();
		
		try {
			t1.join();
			t2.join();
		} catch (InterruptedException e) {}
		
		} else {
			sort(line, begin, middle);
			sort(line, middle + 1, end);
		}
		
		//sort(line, begin, middle); // new task + System.currentTimeMillis()
		//sort(line, middle + 1, end); // new task + System.currentTimeMillis()

		int aux_size = end - begin + 1;
		String[] aux = new String[aux_size];
		int left = begin;
		int right = middle + 1;

		for (int i = 0; i < aux_size; i++) {
			if (right > end	|| (left <= middle && (line[left].compareTo(line[right]) <= 0))) {
				aux[i] = line[left];
				left++;
			} else {
				aux[i] = line[right];
				right++;
			}
		}
		for (int i = 0; i < aux_size; i++)
			line[begin + i] = aux[i];
	}

	public static void main(String[] args) {
		// start time
		
		//computation time: 5.203
		List<String> s = new LinkedList<String>();
		s.add("amor");
		for(int i = 0; i < 500; i++){
			s.add(s.get(s.size()-1) + " " + System.currentTimeMillis());
		}
		
		// start time
		long startTime = System.currentTimeMillis();
		// end time
		new ConcurrentMergeSort().sort(s, " ");
		long endTime = System.currentTimeMillis();
		float time = (endTime - startTime) / 1000.0f;
		System.out.println("computation time: " + time);
		
		//System.out.println(StringTool.arrayToString(new ConcurrentMergeSort().sort(s, " "), "\n"));
	}

	@Override
	public void run() {
		sort(this.array, this.begin, this.end);
	}
	
	public void setArray(String[] array) {
		this.array = array;
	}
	
	public void setBegin(int begin) {
		this.begin = begin;
	}
	
	public void setEnd(int end) {
		this.end = end;
	}

}
